package william.backtracing;

/**
 * @author ZhangShenao
 * @date 2024/4/7
 * @description <a href="https://leetcode.cn/problems/number-of-islands/description/">...</a>
 */
public class Leetcode200_岛屿数量 {
    /**
     * 坐标范围
     */
    private int X;
    private int Y;

    /**
     * 坐标移动方向
     * 按照顺时针方向,依次为上->右->下->左
     */
    private int[][] move = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    /**
     * 记录访问过的坐标
     */
    private boolean[][] visited;

    /**
     * 采用FloodFill算法——递归+回溯实现
     * 遍历二维网格,每遇到一个新的陆地坐标,则将岛屿数量+1,并从该陆地坐标开始,递归标记与它相邻的所有陆地坐标
     * FloodFill算法即模拟洪水从一个点开始逐渐向四周泛滥的过程
     */
    public int numIslands(char[][] grid) {
        //边界条件校验
        if (grid == null || grid.length < 1) {
            return 0;
        }

        //初始化
        X = grid.length;
        Y = grid[0].length;
        visited = new boolean[X][Y];

        //遍历二维网格,每遇到一个新的陆地坐标,则将岛屿数量+1
        //并从该陆地坐标开始,递归标记与它相邻的所有陆地坐标
        int result = 0;
        for (int i = 0; i < X; i++) {
            for (int j = 0; j < Y; j++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    //找到新的陆地坐标,将岛屿数量+1,并从该坐标开始向四周标记陆地
                    result++;
                    dfs(grid, i, j);
                }
            }
        }

        //返回结果
        return result;
    }

    /**
     * 深度优先遍历
     * 以grid[x][y]为起点,标记所有相连的陆地
     */
    private void dfs(char[][] grid, int x, int y) {
        //标记已访问
        visited[x][y] = true;

        //向四周进行FloodFill
        for (int i = 0; i < 4; i++) {
            int newX = x + move[i][0];
            int newY = y + move[i][1];

            //继续标记的条件:新坐标在何方范围内 && 新坐标是陆地 && 新坐标之前未被标记过
            if (isValidPos(newX, newY) && grid[newX][newY] == '1' && !visited[newX][newY]) {
                dfs(grid, newX, newY);
            }
        }
    }

    /**
     * 判断是否为合法的坐标
     */
    private boolean isValidPos(int x, int y) {
        return (x >= 0 && x < X && y >= 0 && y < Y);
    }
}
